package zw_1_100.zw_21_合并两个有序列表;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    public static void main(String[] args) {

        ListNode l1 = new ListNode(0);    //创建首节点
        ListNode nextNode1;                     //声明一个变量用来在移动过程中指向当前节点
        nextNode1=l1;                      //指向首节点
        //创建链表
        for(int i=1;i<4;i++){
            ListNode node1 = new ListNode(3*i-1);  //生成新的节点
            nextNode1.next=node1;               //把心节点连起来
            nextNode1=nextNode1.next;           //当前节点往后移动
        } //当for循环完成之后 nextNode指向最后一个节点，

        nextNode1=l1;                     //重新赋值让它指向首节点
        print(nextNode1);                      //打印输出

        ListNode l2 = new ListNode(1);    //创建首节点
        ListNode nextNode2;                     //声明一个变量用来在移动过程中指向当前节点
        nextNode2=l2;                      //指向首节点
        //创建链表
        for(int i=1;i<4;i++){
            ListNode node2 = new ListNode(2*i);  //生成新的节点
            nextNode2.next=node2;               //把心节点连起来
            nextNode2=nextNode2.next;           //当前节点往后移动
        } //当for循环完成之后 nextNode指向最后一个节点，

        nextNode2=l2;                     //重新赋值让它指向首节点
        print(nextNode2);                      //打印输出


        ListNode mergeTwoLists = mergeTwoLists(l1, l2);
        print(mergeTwoLists);                      //打印输出
    }
    //打印输出方法
    static void print(ListNode listNoed){
        //创建链表节点
        while(listNoed!=null){
            System.out.println("节点:"+listNoed.val);
            listNoed=listNoed.next;
        }
        System.out.println();
    }

    /**
     * 采用递归
     * 根据以上规律考虑本题目：
     * 终止条件：当两个链表都为空时，表示我们对链表已合并完成。
     * 如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。（调用递归）
     * 时间复杂度：O(m+n)
     * m，n为l1和l2的元素个数。递归函数每次去掉一个元素，直到两个链表都为空，因此需要调用R=O(m+n)次。
     * 而在递归函数中我们只进行了 next 指针的赋值操作，复杂度为O(1)，故递归的总时间复杂度为O(T)=R∗O(1)=O(m+n) 。
     * 空间复杂度：O(m+n)
     * 对于递归调用 self.mergeTwoLists()，当它遇到终止条件准备回溯时，已经递归调用了m+n次，使用了m+n个栈帧，故最后的空间复杂度为O(m+n)。
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }

        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
